<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>算法解析：验证二叉搜索树</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', 'Helvetica Neue', Arial, sans-serif;
            background-color: #f8fafc;
            color: #1e293b;
            line-height: 1.6;
        }
        .hero-bg {
            background: linear-gradient(135deg, #f0f9ff 0%, #e0f2fe 100%);
        }
        .code-block {
            background-color: #0f172a;
            border-left: 4px solid #3b82f6;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .drop-cap::first-letter {
            float: left;
            font-size: 4.5rem;
            line-height: 0.65;
            margin: 0.1em 0.1em 0.1em 0;
            color: #3b82f6;
            font-weight: 700;
        }
    </style>
</head>
<body>
    <div class="min-h-screen">
        <!-- Hero Section -->
        <section class="hero-bg py-20 px-4 sm:px-6 lg:px-8">
            <div class="max-w-4xl mx-auto text-center">
                <div class="inline-flex items-center px-4 py-2 rounded-full bg-white shadow-md mb-6">
                    <i class="fas fa-code text-blue-500 mr-2"></i>
                    <span class="text-sm font-medium text-gray-700">算法解析</span>
                </div>
                <h1 class="text-4xl md:text-5xl font-bold text-gray-900 mb-4 font-serif">验证二叉搜索树</h1>
                <p class="text-xl text-gray-600 max-w-3xl mx-auto mb-8">
                    掌握递归和中序遍历两种方法，高效判断二叉树的有效性
                </p>
                <div class="flex flex-wrap justify-center gap-4">
                    <span class="px-4 py-2 bg-blue-500 text-white rounded-full text-sm font-medium">#二叉树</span>
                    <span class="px-4 py-2 bg-indigo-500 text-white rounded-full text-sm font-medium">#递归</span>
                    <span class="px-4 py-2 bg-purple-500 text-white rounded-full text-sm font-medium">#中序遍历</span>
                </div>
            </div>
        </section>

        <!-- Content Section -->
        <section class="py-16 px-4 sm:px-6 lg:px-8">
            <div class="max-w-4xl mx-auto">
                <!-- Problem Description -->
                <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 card-hover transition-all duration-300">
                    <div class="p-6 sm:p-8">
                        <div class="flex items-center mb-4">
                            <i class="fas fa-question-circle text-blue-500 text-xl mr-2"></i>
                            <h2 class="text-2xl font-bold text-gray-900">题目描述</h2>
                        </div>
                        <div class="prose max-w-none text-gray-600">
                            <p class="drop-cap">给定一个二叉树，判断其是否是一个有效的二叉搜索树。二叉搜索树满足：</p>
                            <ol class="list-decimal pl-6 space-y-2">
                                <li>节点的左子树只包含小于当前节点的数</li>
                                <li>节点的右子树只包含大于当前节点的数</li>
                                <li>所有左子树和右子树自身必须也是二叉搜索树</li>
                            </ol>
                            <p class="mt-4">例如，<code class="bg-gray-100 px-2 py-1 rounded">[2,1,3]</code> 是一个有效的二叉搜索树，而 <code class="bg-gray-100 px-2 py-1 rounded">[5,1,4,null,null,3,6]</code> 不是。</p>
                        </div>
                    </div>
                </div>

                <!-- Algorithm Explanation -->
                <div class="grid md:grid-cols-2 gap-8 mb-12">
                    <!-- Recursive Method -->
                    <div class="bg-white rounded-xl shadow-md overflow-hidden card-hover transition-all duration-300">
                        <div class="p-6 sm:p-8">
                            <div class="flex items-center mb-4">
                                <i class="fas fa-sitemap text-indigo-500 text-xl mr-2"></i>
                                <h2 class="text-2xl font-bold text-gray-900">递归法</h2>
                            </div>
                            <div class="prose max-w-none text-gray-600 mb-4">
                                <p>检查每个节点的取值范围，确保左子树所有节点小于当前节点，右子树所有节点大于当前节点。</p>
                                <p class="font-medium text-gray-900">复杂度分析：</p>
                                <ul class="list-disc pl-6 space-y-1">
                                    <li>时间复杂度：O(n)</li>
                                    <li>空间复杂度：O(h)，h为树的高度</li>
                                </ul>
                            </div>
                            <div class="code-block p-4 rounded-lg text-gray-100 overflow-x-auto">
                                <pre><code class="language-python">def isValidBST(root):
    def validate(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)
    
    return validate(root, float('-inf'), float('inf'))</code></pre>
                            </div>
                        </div>
                    </div>

                    <!-- In-order Traversal Method -->
                    <div class="bg-white rounded-xl shadow-md overflow-hidden card-hover transition-all duration-300">
                        <div class="p-6 sm:p-8">
                            <div class="flex items-center mb-4">
                                <i class="fas fa-sort-amount-down text-purple-500 text-xl mr-2"></i>
                                <h2 class="text-2xl font-bold text-gray-900">中序遍历法</h2>
                            </div>
                            <div class="prose max-w-none text-gray-600 mb-4">
                                <p>利用BST的中序遍历结果是递增序列的特性，检查遍历结果是否严格递增。</p>
                                <p class="font-medium text-gray-900">复杂度分析：</p>
                                <ul class="list-disc pl-6 space-y-1">
                                    <li>时间复杂度：O(n)</li>
                                    <li>空间复杂度：O(h)，h为树的高度</li>
                                </ul>
                            </div>
                            <div class="code-block p-4 rounded-lg text-gray-100 overflow-x-auto">
                                <pre><code class="language-python">def isValidBST(root):
    stack, prev = [], float('-inf')
    
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.val <= prev:
            return False
        prev = root.val
        root = root.right
    
    return True</code></pre>
                            </div>
                        </div>
                    </div>
                </div>

                <!-- Visualization Section -->
                <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 card-hover transition-all duration-300">
                    <div class="p-6 sm:p-8">
                        <div class="flex items-center mb-4">
                            <i class="fas fa-project-diagram text-green-500 text-xl mr-2"></i>
                            <h2 class="text-2xl font-bold text-gray-900">算法可视化</h2>
                        </div>
                        <div class="prose max-w-none text-gray-600 mb-6">
                            <p>通过下面的图示理解二叉搜索树的验证过程：</p>
                        </div>
                        <div class="mermaid">
                            graph TD
                                A[5] --> B[1]
                                A --> C[4]
                                C --> D[3]
                                C --> E[6]
                                
                                style A fill:#f0f9ff,stroke:#3b82f6,stroke-width:2px
                                style B fill:#f0f9ff,stroke:#3b82f6,stroke-width:2px
                                style C fill:#fee2e2,stroke:#ef4444,stroke-width:2px
                                style D fill:#fee2e2,stroke:#ef4444,stroke-width:2px
                                style E fill:#fee2e2,stroke:#ef4444,stroke-width:2px
                        </div>
                        <div class="mt-6 bg-blue-50 p-4 rounded-lg">
                            <div class="flex items-start">
                                <i class="fas fa-info-circle text-blue-500 mt-1 mr-2"></i>
                                <p class="text-sm text-blue-800">上图展示了一个无效的二叉搜索树示例。节点4的右子树包含节点3（小于5），违反了二叉搜索树的性质。</p>
                            </div>
                        </div>
                    </div>
                </div>

                <!-- Key Points -->
                <div class="bg-white rounded-xl shadow-md overflow-hidden card-hover transition-all duration-300">
                    <div class="p-6 sm:p-8">
                        <div class="flex items-center mb-4">
                            <i class="fas fa-lightbulb text-yellow-500 text-xl mr-2"></i>
                            <h2 class="text-2xl font-bold text-gray-900">关键要点</h2>
                        </div>
                        <div class="grid sm:grid-cols-2 gap-4">
                            <div class="bg-gray-50 p-4 rounded-lg">
                                <h3 class="font-medium text-gray-900 mb-2 flex items-center">
                                    <i class="fas fa-check-circle text-green-500 mr-2"></i> 边界条件
                                </h3>
                                <p class="text-sm text-gray-600">处理空树情况，以及节点值等于边界值的情况（严格大于/小于）。</p>
                            </div>
                            <div class="bg-gray-50 p-4 rounded-lg">
                                <h3 class="font-medium text-gray-900 mb-2 flex items-center">
                                    <i class="fas fa-arrows-alt-h text-blue-500 mr-2"></i> 递归范围
                                </h3>
                                <p class="text-sm text-gray-600">递归时需要更新左右子树的取值范围，左子树最大值变为当前节点值，右子树最小值变为当前节点值。</p>
                            </div>
                            <div class="bg-gray-50 p-4 rounded-lg">
                                <h3 class="font-medium text-gray-900 mb-2 flex items-center">
                                    <i class="fas fa-sort-numeric-up text-purple-500 mr-2"></i> 中序遍历特性
                                </h3>
                                <p class="text-sm text-gray-600">有效BST的中序遍历结果必须是严格递增序列，相邻元素相等也不符合要求。</p>
                            </div>
                            <div class="bg-gray-50 p-4 rounded-lg">
                                <h3 class="font-medium text-gray-900 mb-2 flex items-center">
                                    <i class="fas fa-infinity text-indigo-500 mr-2"></i> 极值处理
                                </h3>
                                <p class="text-sm text-gray-600">初始调用时使用正负无穷大作为边界，处理可能的节点值为最大/最小整数的情况。</p>
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </section>
    </div>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>